package isInterleave

/*
97. 交错字符串
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
*/

func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n, _mn := len(s1), len(s2), len(s3)
	// 长度加起来都不一样，肯定不是
	if m+n != _mn {
		return false
	}
	// 定义dp数组：对于任意子串∈s1, dp[i]由s1开始，s2[i]个字符能否交替组成s3
	// 假设dp[i]= true， dp[i+1]=true 的条件是 s2[i] == s3[当前s1子串的长度+i]
	dp := make([]bool, n+1)
	dp[0] = true
	var k int
	// 从0开始，是要包含空串
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			// 对于当前s1[i], s2[j]来讲
			// dp[j]是否为true的条件为：
			// 1、 先看s1[i]，继续往s3中添加s1[i]是否可行
			// 2、 s1[i-1] == s3[k] 可行，那么就不用看s2[j]了
			// 3、 不可行，交替为s[j]，往s3中添加s[j]是否可行 s2[j-1] == s3[k]
			// 这里j-1，i-1不是看的上一个，而是当前字符串的个数，因为是从空串开始算的
			k = i + j - 1
			if i > 0 {
				dp[j] = dp[j] && s1[i-1] == s3[k]
			}
			if j > 0 {
				// 与上dp[j] 是看上面if的结果
				dp[j] = dp[j] || dp[j-1] && s2[j-1] == s3[k]
			}
		}
	}
	return dp[n]
}
